
public class demo5 {
    public ListNode partition(ListNode pHead,int x) {
        // write code here

        //去定义两个链表,且用as记录链表的尾部方便插入
        ListNode at=null;
        ListNode as=null;

        ListNode bt=null;
        ListNode bs=null;
        ListNode cut=pHead;
        while(cut!=null){
            if(cut.val<x){
                if(at==null){
                    at=as=cut;
                }
                else{
                    as.next=cut;
                    as=cut;
                }
            }
            else{
                if(bt==null){
                    bt=bs=cut;
                }
                else{
                    bs.next=cut;
                    bs=cut;
                }
            }
            cut=cut.next;
        }
        //还需要判断两种情况
        if(at==null){
            return bt;
        }
        as.next=bt;
        if(bt!=null){
            bs.next=null;
        }

        return at;
    }
}
